import java.util.Iterator;

public class RandomQueue<Item> implements Iterable<Item> {

    int count = 0;
    private Item[] items;
    
    public RandomQueue()
    {
       items = (Item[]) new Object[2];
    }
    
    public boolean isEmpty()
    {
        return count == 0;
    }
    
    public int size()
    {
        return count;
    }
    
    private void reBuild(int size)
    {
        Item[] tmp = (Item[]) new Object[size];
        for(int i = 0; i < count; i++)
        {
            tmp[i] = items[i];
        }
        items = tmp;
    }
    
    public void enqueue(Item item)
    {
        if(count == items.length)
        {
            reBuild(count*2);
        }
        items[count] = item;
        count++;
    }
    
    public Item sample()
    {
        if(count > 0)
        {
            return items[StdRandom.uniform(count)];
        }else{
            throw new RuntimeException("Sampling on a empty list");
        }
    }
    
    public Item dequeue()
    {
        if(count > 0)
        {
            int randompos = StdRandom.uniform(count-1);
            Item tmp = items[randompos];
            items[randompos] = items[count--];
            items[count] = null;
            if(count < items.length/4)
                reBuild(items.length/2);
            return tmp;
        }else{
            throw new RuntimeException("Trying to remove item from empty list");
        }
                
    }
    
    
    
    @Override
    public Iterator<Item> iterator() {
        return new iterator();
    }
    
    class iterator implements Iterator<Item>
    {
        int[] index;
        int pos = 0;

        public iterator() {
           index = new int[count];
           for(int i = 0; i < count; i++)
           {
               index[i] = i;
           }
           StdRandom.shuffle(index);
        }

        @Override
        public boolean hasNext() {
            return pos < index.length;
        }

        @Override
        public Item next() {
            pos++;
            return items[index[pos-1]];
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException("Not supported yet.");
        }
        
    }
    
    public static void main(String args[])
    {
        // Build a queue containing the Integers 1,2,...,6:
        RandomQueue<Integer> Q= new RandomQueue<Integer>();
        for (int i = 1; i < 7; ++i) Q.enqueue(i); // autoboxing! cool!

        // Print 30 die rolls to standard output
        StdOut.print("Some die rolls: ");
        for (int i = 1; i < 30; ++i) StdOut.print(Q.sample() +" ");
        StdOut.println();

        // Let's be more serious: do they really behave like die rolls?
        int[] rolls= new int [10000];
        for (int i = 0; i < 10000; ++i)
          rolls[i] = Q.sample(); // autounboxing! Also cool!
        StdOut.printf("Mean (should be around 3.5): %5.4f\n", StdStats.mean(rolls));
        StdOut.printf("Standard deviation (should be around 1.7): %5.4f\n",
                      StdStats.stddev(rolls));

        // Let's look at the iterator. First, we make a queue of colours:

        RandomQueue<String> C= new RandomQueue<String>();
        C.enqueue("red"); C.enqueue("blue"); C.enqueue("green"); C.enqueue("yellow"); 

        Iterator I = C.iterator();
        Iterator J = C.iterator();

        StdOut.print("Two colours from first shuffle: ");
        StdOut.print(I.next()+" ");
        StdOut.print(I.next()+" ");

        StdOut.print("\nEntire second shuffle: ");
        while (J.hasNext()) StdOut.print(J.next()+" ");

        StdOut.print("\nRemaining two colours from first shuffle: ");
        StdOut.print(I.next()+" ");
        StdOut.println(I.next());
    }

    
}
